package problem44_Wildcard_Matching;

public class MySolution {
	 public boolean isMatch(String s, String p) {
	     boolean[] matches=new boolean[s.length()+1];
	     matches[s.length()]=true;
	     char[] chars=p.toCharArray();
	     for(int j=chars.length-1;j>=0;j--){
	    	 char pi=chars[j];
	    	 if(pi=='*'){
	    		 for(int i=s.length();i>0;i--){
	    			 matches[i-1]=matches[i-1]||matches[i];
	    		 }
	    	 }else{
	    		 for(int i=0;i<s.length();i++){
	    			 matches[i]=matches[i+1]&&(pi==s.charAt(i)||(pi=='?'&&Character.isLetter(s.charAt(i))));
	    		 }
	    		 matches[s.length()]=false;
	    	 }
	     }
	     return matches[0];
	 }
	 
	 public static void main(String[] ags){
		 System.out.println(new MySolution().isMatch("abecdgimde", "ab*cd?i*de"));
	 }
}
